package leetcode.p21;

import leetcode.ListNode;

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //合并两个有序链表
        ListNode cur1=l1;
        ListNode cur2=l2;

        //结果链表引入哨兵结点last
        ListNode last=new ListNode(-1);
        //引入结果链表始终不动的头结点
        ListNode newHead=last;

        while (cur1!=null && cur2!=null) {
            if(cur1.val<=cur2.val) {
                //把cur1尾插到结果链表中
                last.next=cur1;
                last=cur1;
                cur1=cur1.next;
            }else {
                //把cur2尾插到结果链表中
                last.next=cur2;
                last=cur2;
                cur2=cur2.next;
            }
        }

        if(cur1 != null) {
            last.next=cur1;
        }else {
            last.next=cur2;
        }

        return newHead.next;

    }

}
